package com.demo.function.arithmetic;

import java.util.List;

/**
 * 二分查找算法
 * <a href="https://blog.csdn.net/maoyuanming0806/article/details/78176957">https://blog.csdn.net/maoyuanming0806/article/details/78176957</a>
 */
public class BinarySearch {

    /**
     * 使用递归的二分查找
     *@param list 有序数组
     *@param key 待查找关键字
     *@return 找到的位置
     */
    public static int recursionBinarySearch(List<Integer> list, int key, int low, int high){

        if(key < list.get(low) || key > list.get(high) || low > high){
            return -1;
        }

        //初始中间位置
        int middle = (low + high) / 2;
        if(list.get(middle) > key){
            //比关键字大则关键字在左区域
            return recursionBinarySearch(list, key, low, middle - 1);
        }else if(list.get(middle) < key){
            //比关键字小则关键字在右区域
            return recursionBinarySearch(list, key, middle + 1, high);
        }else {
            return middle;
        }
    }

    /**
     * 不使用递归的二分查找
     *@param list 查找集合
     *@param key  搜索关键字
     *@return 关键字位置
     */
    public static int commonBinarySearch(List<Integer> list,int key){
        int low = 0;
        int high = list.size() - 1;
        //定义middle
        int middle;

        if(key < list.get(low) || key > list.get(high)){
            return -1;
        }

        while(low <= high){
            middle = (low + high) / 2;
            if(list.get(middle) > key){
                //比关键字大则关键字在左区域
                high = middle - 1;
            }else if(list.get(middle) < key){
                //比关键字小则关键字在右区域
                low = middle + 1;
            }else{
                return middle;
            }
        }
        //最后仍然没有找到，则返回-1
        return -1;
    }
}
